package com.github.yangyishe.p100;

import java.util.Arrays;

/**
 * 52. N 皇后 II
 * https://leetcode.cn/problems/n-queens-ii/description/?envType=study-plan-v2&envId=top-interview-150
 *
 * n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。
 *
 * 给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：n = 4
 * 输出：2
 * 解释：如上图所示，4 皇后问题存在两个不同的解法。
 * 示例 2：
 *
 * 输入：n = 1
 * 输出：1
 *
 *
 * 提示：
 *
 * 1 <= n <= 9
 */
public class Problem52 {
    public static void main(String[] args) {
        int n=4;

        Problem52 problem52 = new Problem52();
        int i = problem52.totalNQueens(n);
        System.out.println(i);
    }

    /**
     * 思路:
     * 参考韩顺平老师的讲解
     * @param n
     * @return
     */
    public int totalNQueens(int n) {
        int[] currentBoard=new int[n];

        iterate(currentBoard,0);

        return count;
    }

    private int count;

    private void iterate(int[] currentBoard,int cx){
        if(cx==currentBoard.length){
            count++;
            return;
        }
        boolean flag;
        for(int cy=0;cy<currentBoard.length;cy++){
            flag=false;
            for(int i=0;i<cx;i++){
                if(currentBoard[i]==cy){
                    flag=true;
                    break;
                }
                if(Math.abs(cx-i)==Math.abs(cy-currentBoard[i])){
                    flag=true;
                    break;
                }
            }
            if(!flag){
                currentBoard[cx]=cy;
                iterate(currentBoard,cx+1);
            }

        }

    }
}
